package leetcode_ago.bin_tree;

/**
 * 平衡二叉树：给定一个二叉树，判断它是否是高度平衡的二叉树。
 * 本题中，一棵高度平衡二叉树定义为一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1
 * Math.abs():计算差值
 * 思路：1.计算二叉树高度 2.看高度的差值进行判断
 */
//public class Num110_BalanceTree {
//    public boolean isBalanced(TreeNode root) {
//        if(root==null){
//            return true;
//        }
//        int left=height(root.left);
//        int right=height(root.right);
//        int abs=Math.abs(left-right);
//        if(abs>1){
//            return false;
//        }
//        //此时差值<=1,计算左右子树是否高度平衡
//        return isBalanced(root.left)&&isBalanced(root.right);
//    }
//
//    private int height(TreeNode root) {
//        if(root==null){
//            return 0;
//        }
//        return 1+Math.max(height(root.left),height(root.right));
//    }
//}

import java.util.HashMap;
import java.util.Map;

/**
 * 记忆化搜索进行优化：
 * 在递归过程中，若某个节点的高度已经被计算过了，我们就使用Map存储该节点以及其高度值
 * 下次再用到这个节点的时候，我们直接从Map中取高度即可，避免多次重复的递归过程
 */
public class Num110_BalanceTree {
    private Map<TreeNode,Integer> highMap=new HashMap<>();//Map集合存储二叉树对应的高度
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int left=0;
        int right=0;//先不着急给left,right赋值
        //先再Map集合中搜索子树高度是否存在
        //存在直接赋值，不存在再求子树高度并加入Map集合
        if(highMap.containsKey(root.left)){//左子树高度存在在集合中
            left=highMap.get(root.left);//从集合中直接取出高度
        }else{
            left=height(root.left);
            highMap.put(root.left,left);
        }
        if(highMap.containsKey(root.right)){
            right=highMap.get(root.right);
        }else{
            right=height(root.right);//求右子树高度
            highMap.put(root.right,right);//右子树高度加入Map集合
        }
        if(Math.abs(left-right)>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }

    private int height(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(height(root.left),height(root.right));
    }
}